package com.hanlin.day04;

/**
 * 描述：链表
 *
 * @author:hl.yuan
 * @date:2022-06-13
 */
public class LinkedList {

    public static void main(String[] args) {
        Node n1 = new Node(1);
        n1.next = new Node(2);
        n1.next.next = new Node(3);
        n1 = flashbackLinkedList(n1);
        while (n1 != null) {
            System.out.print(n1.value + " ");
            n1 = n1.next;
        }
        System.out.println();
        System.out.println("******************************************");
        DoubleNode doubleNode = new DoubleNode(1);
        doubleNode.next = new DoubleNode(2);
        doubleNode.next.last = doubleNode;
        doubleNode.next.next = new DoubleNode(3);
        doubleNode.next.next.last = doubleNode.next;
        doubleNode = flashbackLinkedList(doubleNode);

        while (doubleNode != null) {
            System.out.print(doubleNode.value + " ");
            doubleNode = doubleNode.next;
        }
    }

    /**
     * 对单链表进行倒叙
     *
     * @return
     */
    public static Node flashbackLinkedList(Node node) {
        // 之前的节点
        Node pre = null;
        // 下一个节点
        Node next = null;
        while (node != null) {
            // 把当前链表的下一个指向的对象，记录在next里
            next = node.next;
            // 把记录下的来的上一个对象，放在当前链表的下一个对象里
            node.next = pre;
            // 记录本次对象
            pre = node;
            // 把当前对象的指针向下移动
            node = next;
        }
        // 主要这里是返回，链表的头节点！如果不返回，链表相当于没有改，
        // 比如 之前的链表是 1 2 3 ，然后倒叙后，变成了 3 2 1，
        // 但是 链表的头节点还是1，所以会导致3和2找不到，这样JVM就会把3和2给回收。jvm：根可达算法
        return pre;
    }

    /**
     * 双向链表倒叙
     *
     * @param head
     * @return
     */
    public static DoubleNode flashbackLinkedList(DoubleNode head) {
        // 记录上一个节点
        DoubleNode pre = null;
        // 记录下一个节点
        DoubleNode next = null;
        while (head != null) {
            // 用next记录下一个节点
            next = head.next;
            // 那per赋值给head的下一个节点
            head.next = pre;
            // head的上一个节点要指向 next
            head.last = next;

            pre = head;
            // 把next（下一个节点） 赋值给head
            head = next;
        }
        return pre;
    }
}

/**
 * 链表结构
 */
class Node {
    public Node next;
    public int value;

    public Node() {
    }

    public Node(int value) {
        this.value = value;
    }
}

/**
 * 双向链表
 */
class DoubleNode {
    public int value;
    public DoubleNode last;
    public DoubleNode next;

    public DoubleNode(int value) {
        this.value = value;
    }
}
